import java.util.*;

public class Solution {
    /**
     * 两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if (hash.get(target - nums[i]) != null) {
                return new int[]{hash.get(target - nums[i]), i};
            } else {
                hash.put(nums[i], i);
            }
        }
        return new int[2];
    }

    /**
     * 存在重复元素
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) != null) {
                return true;
            } else {
                hash.put(nums[i], i);
            }
        }
        return false;
    }

    /**
     * 存在重复元素II
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) != null
                    && (i - hash.get(nums[i]) <= k)) {
                return true;
            } else {
                hash.put(nums[i], i);
            }
        }
        return false;
    }

    /**
     * 字母异位词分组
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for(int i = 0; i < strs.length; i++) {
            char[] chs = strs[i].toCharArray();
            Arrays.sort(chs);
            String key = new String(chs);
            if (hash.get(key) != null) {
                hash.get(key).add(strs[i]);
            } else {
                hash.put(key, new ArrayList<>(Arrays.asList(strs[i])));
            }
        }
        List<List<String>> res = new ArrayList<>();
        for(String str: hash.keySet()) {
            res.add(hash.get(str));
        }
        return res;
    }
}
